import java.util.ArrayList;
import java.util.Stack;

public class Graph {
	private int _n; //row
	private int _m; // column
	protected ArrayList<Vertex> vertices;
	protected int[][] dismat = null;
	protected int[][] mat = null;
	int flag = 0;
	protected Stack<Vertex> tracer = new Stack<Vertex>();

	public Graph(Maze ma) {
		this._n = ma.get_n() + 2; // Create border around the matrix
		this._m = ma.get_m() + 2; //
		this.vertices = new ArrayList<Vertex>();
		this.mat = new int[this._n][this._m];
		for (int i = 0; i < _n - 2; i++) {
			for (int j = 0; j < _m - 2; j++) {
				if (ma.mat[i][j] == '.')
					this.mat[i + 1][j + 1] = 1;
				else
					this.mat[i + 1][j + 1] = 0;
			}
		}
	}

	public Graph(int n, int m) {
		this._n = n;
		this._m = m;
		this.mat = new int[n][m];
	}

	public boolean moveNext(int i, int j) {
		if ((mat[i][j - 1] == 1))
			return true;
		else if ((mat[i + 1][j] == 1))
			return true;
		else if ((mat[i][j + 1] == 1))
			return true;
		else if ((mat[i - 1][j] == 1))
			return true;
		return false;
	}

	public boolean notExistInVertices(Vertex u) {
		for (Vertex v : vertices) {
			if (v.equals(u))
				return false;
		}
		return true;
	}

	public void move2(Vertex v) {
		int i, j;
		int dis = 0;
		i = v.x + 1;
		j = v.y + 1;
		tracer.push(v);
		while (true) {
			if (moveNext(i, j)) {
				if ((mat[i][j - 1] == 1)) {
					mat[i][j] = 2;
					j--;
					dis++;
				} else if ((mat[i + 1][j] == 1)) {
					mat[i][j] = 2;
					i++;
					dis++;
				} else if ((mat[i][j + 1] == 1)) {
					mat[i][j] = 2;
					j++;
					dis++;
				} else if ((mat[i - 1][j] == 1)) {
					mat[i][j] = 2;
					i--;
					dis++;
				}
			} else {
				// not move: check isVertex,
				if (isVertex(i, j)) {
					if (!tracer.isEmpty()) {
						tracer.pop();
						if (!tracer.isEmpty()) {
							i = tracer.peek().x + 1;
							j = tracer.peek().y + 1;
						} else
							break;
						continue;
					} else {
						break; // Condition for stop while loop
					}

				} else {
					dis++;
					mat[i][j] = 2;
					
					if (isVertex(i, j - 1)) {
						Vertex u = new Vertex(_m - 2, i - 1, j - 2);
						dismat[vertices.indexOf(tracer.peek())][indexInVertices(u)] = dis;
						dismat[indexInVertices(u)][vertices.indexOf(tracer.peek())] = dis;
						dis = 0;
						if (!tracer.isEmpty()) {
							i = tracer.peek().x + 1;
							j = tracer.peek().y + 1;
						}
						
					}
					else if (isVertex(i+1, j )) {
						Vertex u = new Vertex(_m - 2, i , j -1);
						dismat[vertices.indexOf(tracer.peek())][indexInVertices(u)] = dis;
						dismat[indexInVertices(u)][vertices.indexOf(tracer.peek())] = dis;
						dis = 0;
						if (!tracer.isEmpty()) {
							i = tracer.peek().x + 1;
							j = tracer.peek().y + 1;
						}
					}
					else if (isVertex(i-1, j )) {
						Vertex u = new Vertex(_m - 2, i-2 , j -1);
						dismat[vertices.indexOf(tracer.peek())][indexInVertices(u)] = dis;
						dismat[indexInVertices(u)][vertices.indexOf(tracer.peek())] = dis;
						dis = 0;
						if (!tracer.isEmpty()) {
							i = tracer.peek().x + 1;
							j = tracer.peek().y + 1;
						}
					}
					else if (isVertex(i, j+1 )) {
						Vertex u = new Vertex(_m - 2, i-1 , j);
						dismat[vertices.indexOf(tracer.peek())][indexInVertices(u)] = dis;
						dismat[indexInVertices(u)][vertices.indexOf(tracer.peek())] = dis;
						dis = 0;
						if (!tracer.isEmpty()) {
							i = tracer.peek().x + 1;
							j = tracer.peek().y + 1;
						}
					}
				}
			}
			if (isVertex(i, j)) {
				mat[i][j] = 2;
				Vertex u = new Vertex(_m - 2, i - 1, j - 1);
				if (notExistInVertices(u) == true) {
					vertices.add(u);
					dismat[vertices.indexOf(tracer.peek())][vertices.indexOf(u)] = dis;
					dismat[vertices.indexOf(u)][vertices.indexOf(tracer.peek())] = dis;
					dis = 0;
					tracer.push(u);
				}
			}
		}
	}

	public int indexInVertices(Vertex v) {
		for (Vertex u : vertices) {
			if (u.equals(v))
				return vertices.indexOf(u);
		}
		return -1;
	}

	@Override
	public String toString() {
		String str = "";
		for (int i = 0; i < vertices.size(); i++) {
			for (int j = 0; j < vertices.size(); j++) {
				str += this.dismat[i][j];
				str += "\t";
			}

			str += "\n";
		}
		return str;
	}

	public boolean isVertex(int i, int j) {
		if (mat[i][j] != 0) {
			if (mat[i][j - 1] != 0) {
				if (mat[i + 1][j] != 0) {
					if (mat[i][j + 1] != 0) {
						if (mat[i - 1][j] != 0) {
							return true; // 4 directions
						} else {
							return true; // 3 directions
						}
					} else {
						if (mat[i - 1][j] != 0) {
							return true; // 3 directions
						} else {
							return false;// 2 directions
						}
					}
				} else {
					if (mat[i][j + 1] != 0) {
						if (mat[i - 1][j] != 0) {
							return true; // 3 directions
						} else {
							return false;// 2 directions
						}
					} else {
						if (mat[i - 1][j] != 0) {
							return false;// 2 directions
						} else {
							return true; // 1 direction
						}
					}
				}
			} else {
				if (mat[i + 1][j] != 0) {
					if (mat[i][j + 1] != 0) {
						if (mat[i - 1][j] != 0) {
							return true; // 3 directions
						} else {
							return false;// 2 directions
						}
					} else {
						if (mat[i - 1][j] != 0) {
							return false;// 2 directions
						} else {
							return true; // 1 direction
						}
					}
				} else {
					if (mat[i][j + 1] != 0) {
						if (mat[i - 1][j] != 0) {
							return false;// 2 directions
						} else {
							return true; // 1 direction
						}
					} else {
						if (mat[i - 1][j] != 0) {
							return true; // 1 direction
						} else {
							return false;// 0 direction
						}
					}
				}
			}
		} else {
			return false;
		}
	}

	public int get_n() {
		return _n;
	}

	public void set_n(int _n) {
		this._n = _n;
	}

	public int get_m() {
		return _m;
	}

	public void set_m(int _m) {
		this._m = _m;
	}

}
